//
//  Problem1685.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/5/24.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1685. 有序数组中差绝对值之和
 给你一个 非递减 有序整数数组 nums 。

 请你建立并返回一个整数数组 result，它跟 nums 长度相同，且result[i] 等于 nums[i] 与数组中所有其他元素差的绝对值之和。

 换句话说， result[i] 等于 sum(|nums[i]-nums[j]|) ，其中 0 <= j < nums.length 且 j != i （下标从 0 开始）。

 示例 1：
     输入：nums = [2,3,5]
     输出：[4,3,5]
     解释：假设数组下标从 0 开始，那么
     result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4，
     result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3，
     result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。
 示例 2：
     输入：nums = [1,4,6,8,10]
     输出：[24,15,13,15,21]

 提示：
     2 <= nums.length <= 105
     1 <= nums[i] <= nums[i + 1] <= 104
 */
@objcMembers class Problem1685: NSObject {
    func solution() {
        print(getSumAbsoluteDifferences([2,3,5]))
        print(getSumAbsoluteDifferences([1,4,6,8,10]))
    }
    
    /*
     前缀和
     我们要使用的是：非递减 这个特性
     非递减：意味着i的左侧都小于等于i的值
     => [0..i-1] <= [i], 那么我们求的左侧的绝对值和可以转换成
     => [i]-[0] + [i]-[1] + .. + [i]-[i-1]  我们把[i] 提出来
     => [i] * i - ([0] + [1] + .. + [i-1])  后面的括号不就是 [i-1] 的前缀和
     同理 i 的右侧都是大于等于i的值
     => [i] <= [i+1..n-1], 那么我们求的右侧的绝对值和可以转换成
     => [i+1]-[i] + [i+2]-[i] + .. + [n-1]-[i]  我们把[i] 提出来
     => ([i+1] + [i+2] + .. + [n-1]) - [i] * (n-1-i)  前面的括号不就是 [n-1]的前缀和 - [i]的前缀和
     
     所有我们先计算出前缀和，然后把2部分相加即可
     [i]*i - sum[i-1] + sum[n-1] - sum[i] - [i]*(n-1-i)
     => [i]*(2i-n+1) + sum[n-1] - sum[i] - sum[i-1]
     => [i]*(2i-n+1) + sum[n-1] - sum[i] - (sum[i] - [i])
     => [i]*(2i-n+2) + sum[n-1] - 2*sum[i]
     
     验证 [2,3,5]
     2 * (2*0-3+2) + 10 - 2*2 = 4
     3 * (2*1-3+2) + 10 - 2*5 = 3
     5 * (2*2-3+2) + 10 - 2*10 = 5
     
     */
    func getSumAbsoluteDifferences(_ nums: [Int]) -> [Int] {
        let n = nums.count
        
        var pSum:[Int] = Array(repeating: 0, count: n)
        pSum[0] = nums[0]
        for i in 1..<n {
            pSum[i] = pSum[i-1] + nums[i]
        }
        
        
        var result:[Int] = Array(repeating: 0, count: n)
        for i in 0..<n {
            result[i] = nums[i] * (2 * i - n + 2) + pSum[n-1] - 2 * pSum[i]
        }
        return result
    }
}
